Breadth First Search (BFS) for Graph

Description

Breadth First Traversal (or Search) for a graph is similar to Breadth First
Traversal of a tree (See method 2 of this post). The only catch here is,
unlike trees, graphs may contain cycles, so we may come to the same node
again. To avoid processing a node more than once, we use a boolean visited
array. For simplicity, it is assumed that all vertices are reachable from
the starting vertex.
For example, in the following graph, we start traversal from vertex 2.
When we come to vertex 0, we look for all adjacent vertices of it.
2 is also an adjacent vertex of 0.
If we don’t mark visited vertices, then 2 will be processed again and it
will become a non-terminating process.
See: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

 from collections import defaultdict

 # This class represents a directed graph
 # using adjacency list representation
 class Graph:

     # Constructor
     def __init__(self):
         ''' default dictionary to store graph '''
         self.graph = defaultdict(list)

     def addEdge(self, u, v):
         ''' add an Edge to graph'''
         self.graph[u].append(v)
         # after adding all edges:
         # Graph: defaultdict(<class 'list'>, \
         {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]})

     def BFS(self, s):
         ''' Mark all the Vertices as not visited '''
         visited = [False] * (len(self.graph))

         # Create a queue for BFS
         queue = []
         # Mark the source node as visited and enqueue it
         queue.append(s)
         visited[s] = True

         while queue:
             # Dequeue a Vertex from queue and print it
             s = queue.pop(0)
             print(str(s) + " -> ", end="")

             # Get all adjacent Vertices of the dequeued Vertex s.
             # If a adjacent has not been visited, then mark it
             # visited and enqueue it
             for i in self.graph[s]:
                 if visited[i] == False:
                     queue.append(i)
                     visited[i] = True

# test
#
#  Graph
#         0  ----> 1
#         ^ |     /
#         | |    /
#         | |   /    +---+
#         | |  /     |   |
#         | v v      v   |
# start-> 2 -------> 3 --+

g = Graph()
g.addEdge(0, 1)    # 0 --> 1
g.addEdge(0, 2)    # 0 --> 2
g.addEdge(1, 2)    # 1 --> 2
g.addEdge(2, 0)    # 2 --> 0
g.addEdge(2, 3)    # 2 --> 3
g.addEdge(3, 3)    # 3 <-> 3

print("Following is Breadth First Traversal"
      " (starting from vertex 2)")
g.BFS(2)                                     # 2 0 3 1